package com.maltys.dp.house.robber;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/house-robber-ii/">打家劫舍II</a>
 */
public class HouseRobberII {
    public static void main(String[] args) {
        HouseRobberII robberII = new HouseRobberII();
        int rob = robberII.rob(new int[]{2, 3, 2});
        System.out.println(rob);
    }

    public int rob(int[] nums) {
        int doRob1 = doRob(nums, 0, nums.length - 2);
        int doRob2 = doRob(nums, 1, nums.length - 1);
        return Math.max(doRob2, doRob1);
    }

    private int doRob(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int[] dp = new int[end - start + 1];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i - start] = Math.max(dp[i - start - 1], dp[i - start - 2] + nums[i]);
        }
        return dp[end - start];
    }
}
